// 2025/3/19
// https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked
// 组合总和

class Solution {
    public:
        vector<int> tmp;
        vector<vector<int>> ans;
    
        void dfs(vector<int>& candidates, int target, int pos)
        {
            if (target <= 0 || pos == candidates.size())
            {
                if (target == 0) ans.push_back(tmp);
                return;
            }
    
            int m = target / candidates[pos];
            for (int i = 0; i <= m; i++)
            {
                dfs(candidates, target - candidates[pos] * i, pos + 1);
                tmp.push_back(candidates[pos]);
            }
            for (int i = 0; i <= m; i++)
                tmp.pop_back();
        }
    
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
            dfs(candidates, target, 0);
            return ans;
        }
    };

